Stack, Queue

2022년 09월 29일

비원시 자료구조, 선형적 자료구조

스택(Stack) 과 큐(Queue) 는 비원시 자료구조(Non-Primitive Data Structure) 이며, 선형적 자료구조(Linear Structure) 이다. 먼저 이것이 무엇일까?

원시 자료구조가 정수형(Integer), 실수형(Float), 문자형(Character)과 같은 자료 구성의 기본 단위라면, 비원시 자료구조는 Stack, Queue, Linked List처럼 한 번에 여러 값을 가지며 고정되지 않은 동적 공간을 사용하는 데이터 구조 유형이다. 컴퓨터 과학에서는 자료 연산에 구체적인 방법을 명시하지 않는다는 부분에서 추상 자료형(Abstact Data Type) 이라고도 한다.

또한 비원시 자료구조는 선형 구조와 비선형 구조로 분류된다.

선형 구조(linear) : 데이터 구조의 순차 유형으로, 1:1의 관계를 가짐.
- ex ) Stack, Queue, Linked List, Deque
비선형 구조(Nonlinear) : 무작위 자료구조 형태이며, 데이터가 1:n 또는 n:n 관계를 가짐.
- ex ) Tree, Graph

이 중에서 Stack과 Queue를 javascript로 간단하게 구현해 보았다.

Stack

stack1

책을 쌓는 것처럼 차곡차곡 쌓아 올린 형태의 자료구조를 Stack이라고 한다.

한 쪽 끝에서만 자료를 넣고 뺄 수 있으므로 Last In First Out(LIFO) 형식이라고 부른다. 따라서 마지막으로 들어온 값, 나중에 넣은 값이 먼저 나오게 된다.

Stack은 push()와 pop()을 사용하여 javascript로 쉽게 구현할 수 있는데,

// stack
const stack = []

function addStack(item) {
  stack.push(item)
}

function delStack() {
  stack.pop()
}

addStack(1)
addStack(2)
addStack(3)
addStack(4)

delStack()

console.log(`stack = ${stack}`)

javascript의 pop() 함수는 배열의 가장 맨 끝 값을 제거해 준다.
addStack으로 값을 추가, delStack은 가장 마지막에 push되었던 값 4를 제거하며 최종적으로 1,2,3이 남아있는 것을 볼 수 있다.

stack2

Stack의 LIFO 원리는 이전의 작업 내용을 저장해 둘 필요한 경우에 활용 될 수 있다.

웹 브라우저 방문 기록 - 가장 나중에 열린 페이지부터 방문 리스트에 표시
역순 문자열 만들기 - 가장 나중에 입력된 문자부터 출력
실행 취소 (undo) - 가장 나중에 실행된 것부터 취소
재귀 알고리즘 - stack에 담아 두었던 재귀 함수를 backtrack 시 임시 데이터를 빼주는 형식
후위 표기법 계산 - postfix notation
수식의 괄호 검사 - 연산자 우선순위 표현을 위한 괄호 검사

Queue

queue1

Queue는 한쪽으로 데이터를 넣고 다른 쪽으로 데이터를 가져오는 구조이다.

맨 처음 입력된 데이터가 먼저 나오게 된다. First In First Out(FIFO), Last In Last Out(LILO) 형식으로 불린다.

// queue
const queue = []

function addQueue(item) {
  queue.push(item)
}

function delQueue() {
  queue.shift()
}

addQueue(1)
addQueue(2)
addQueue(3)
addQueue(4)

delQueue()

console.log(`queue = ${queue}`)